package leetcode1;

import java.util.HashMap;
import java.util.Map;

public class Day19 {
    public static void main(String[] args) {
        //.out.println(integerReplacement(7));
    }
    Map<Long,Integer> memo = new HashMap<>();
    public int integerReplacement(int n) {
        return dfs(n*1l);
    }
    int dfs(long n) {
        if(n == 1) return 0;
        if(memo.getOrDefault(n,-1) != -1) return memo.get(n);
        int tmp = 1;
        if(n%2==0) {
            tmp += dfs(n/2);
        }else {
            tmp += Math.min(dfs(n-1),dfs(n+1));
        }
        memo.put(n,tmp);//n到1的最小步数
        return tmp;
    }
}
